home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / zoo / maketree.c < prev    next >
C/C++ Source or Header  |  1980-01-02  |  3KB  |  132 lines
  1. /*$Source: /usr/home/dhesi/zoo/RCS/maketree.c,v $*/
  2. /*$Id: maketree.c,v 1.6 91/07/09 01:39:51 dhesi Exp $*/
  3. /***********************************************************
  4.     maketree.c -- make Huffman tree
  5.  
  6. Adapted from "ar" archiver written by Haruhiko Okumura.
  7. ***********************************************************/
  8. #include "options.h"
  9. #include "zoo.h"
  10. #include "ar.h"
  11. #include "lzh.h"
  12.  
  13. static int      n, heapsize;
  14. static short  heap[NC + 1];
  15. static ushort *freq, *sortptr, len_cnt[17];
  16. static uchar  *len;
  17.  
  18. static void count_len PARMS((int));
  19. static void downheap PARMS((int));
  20. static void make_len PARMS((int));
  21. static void make_code PARMS((int, uchar *, ushort *));
  22.  
  23. static void count_len(i)  /* call with i = root */
  24. int i;
  25. {
  26.     static int depth = 0;
  27.  
  28.     if (i < n) len_cnt[(depth < 16) ? depth : 16]++;
  29.     else {
  30.         depth++;
  31.         count_len((int) left [i]);
  32.         count_len((int) right[i]);
  33.         depth--;
  34.     }
  35. }
  36.  
  37. static void make_len(root)
  38. int root;
  39. {
  40.     int i, k;
  41.     uint cum;
  42.  
  43.     for (i = 0; i <= 16; i++) len_cnt[i] = 0;
  44.     count_len(root);
  45.     cum = 0;
  46.     for (i = 16; i > 0; i--)
  47.         cum += len_cnt[i] << (16 - i);
  48.     while (cum != ((unsigned) 1 << 16)) {
  49.         (void) fprintf(stderr, "17");
  50.         len_cnt[16]--;
  51.         for (i = 15; i > 0; i--) {
  52.             if (len_cnt[i] != 0) {
  53.                 len_cnt[i]--;    len_cnt[i+1] += 2;  break;
  54.             }
  55.         }
  56.         cum--;
  57.     }
  58.     for (i = 16; i > 0; i--) {
  59.         k = len_cnt[i];
  60.         while (--k >= 0) len[*sortptr++] = i;
  61.     }
  62. }
  63.  
  64. static void downheap(i)
  65. int i;
  66.     /* priority queue; send i-th entry down heap */
  67. {
  68.     int j, k;
  69.  
  70.     k = heap[i];
  71.     while ((j = 2 * i) <= heapsize) {
  72.         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  73.             j++;
  74.         if (freq[k] <= freq[heap[j]]) break;
  75.         heap[i] = heap[j];  i = j;
  76.     }
  77.     heap[i] = k;
  78. }
  79.  
  80. static void make_code(j, length, code)
  81. int j;
  82. uchar length[];
  83. ushort code[];
  84. {
  85.     int     i;
  86.     ushort start[18];
  87.  
  88.     start[1] = 0;
  89.     for (i = 1; i <= 16; i++)
  90.         start[i + 1] = (start[i] + len_cnt[i]) << 1;
  91.     for (i = 0; i < j; i++) code[i] = start[length[i]]++;
  92. }
  93.  
  94. int make_tree(nparm, freqparm, lenparm, codeparm)
  95. int nparm;
  96. ushort freqparm[];
  97. uchar lenparm[];
  98. ushort codeparm[];
  99.     /* make tree, calculate len[], return root */
  100. {
  101.     int i, j, k, avail;
  102.  
  103.     n = nparm;    freq = freqparm;    len = lenparm;
  104.     avail = n;    heapsize = 0;    heap[1] = 0;
  105.     for (i = 0; i < n; i++) {
  106.         len[i] = 0;
  107.         if (freq[i]) heap[++heapsize] = i;
  108.     }
  109.     if (heapsize < 2) {
  110.         codeparm[heap[1]] = 0;    return heap[1];
  111.     }
  112.     for (i = heapsize / 2; i >= 1; i--)
  113.         downheap(i);  /* make priority queue */
  114.     sortptr = codeparm;
  115.     do {    /* while queue has at least two entries */
  116.         i = heap[1];  /* take out least-freq entry */
  117.         if (i < n) *sortptr++ = i;
  118.         heap[1] = heap[heapsize--];
  119.         downheap(1);
  120.         j = heap[1];  /* next least-freq entry */
  121.         if (j < n) *sortptr++ = j;
  122.         k = avail++;  /* generate new node */
  123.         freq[k] = freq[i] + freq[j];
  124.         heap[1] = k;  downheap(1);  /* put into queue */
  125.         left[k] = i;  right[k] = j;
  126.     } while (heapsize > 1);
  127.     sortptr = codeparm;
  128.     make_len(k);
  129.     make_code(nparm, lenparm, codeparm);
  130.     return k;  /* return root */
  131. }
  132.